/*
*

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数：

给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
总成本必须恰好等于 target 。
添加的数位中没有数字 0 。
由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 "0" 。

示例 1：

输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出："7772"
解释：添加数位 '7' 的成本为 2 ，添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "977" 也是满足要求的数字，但 "7772" 是较大的数字。

	数字     成本
	 1  ->   4
	 2  ->   3
	 3  ->   2
	 4  ->   5
	 5  ->   6
	 6  ->   7
	 7  ->   2
	 8  ->   5
	 9  ->   5

示例 2：

输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出："85"
解释：添加数位 '8' 的成本是 7 ，添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。
示例 3：

输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出："0"
解释：总成本是 target 的条件下，无法生成任何整数。
示例 4：

输入：cost = [6,10,15,40,40,40,40,40,40], target = 47
输出："32211"

提示：

cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000

  - @author ala
  - @date 2024-10-11 17:47
*/
package main

import (
	"fmt"
	"strconv"
)

func main() {
	cost := []int{4, 3, 2, 5, 6, 7, 2, 5, 5}
	target := 9

	fmt.Println(largestNumber(cost, target))
}

func largestNumber(cost []int, target int) string {
	return V1(cost, target)
}

/**
 *	1）dp[i] = [9]int：表示成本为i时，能组合出的最大数字，中的每个数出现多少次
 *	2）dp[0] = {全0}
 *		dp[i] = max(dp[i - cost[j]] + j)
 *  3）提供比较dp的函数
 *	4）最后dp[target]按最高位倒序出来就是答案
 */
func V1(cost []int, target int) string {
	dp := make([][]int, target+1)
	cnts := make([]int, target+1)
	for i := range dp {
		dp[i] = make([]int, 9)
	}

	for i, c := range cost {
		for t := c; t <= target; t++ {
			//	减少复制次数，先在原数组上改，完了再改回来
			dp[t-c][i]++
			cnts[t-c]++
			//	数字多的一定比数字少的大，数字一样多再比较谁有的数字大
			if (cnts[t-c] >= cnts[t]) && (compare(dp[t-c], dp[t]) > 0) {
				cnts[t] = cnts[t-c]
				copy(dp[t], dp[t-c])
			}
			dp[t-c][i]--
			cnts[t-c]--
		}
	}

	return toString(dp[target])
}

/**
 *	比较两个[9]int
 */
func compare(a, b []int) int {
	for i := 8; i >= 0; i-- {
		if a[i] > b[i] {
			return 1
		} else if a[i] < b[i] {
			return -1
		}
	}
	return 0
}

/**
 *	转为字符串
 */
func toString(nums []int) string {
	s := ""
	for i := 8; i >= 0; i-- {
		n := nums[i]
		for n > 0 {
			s = s + strconv.Itoa(i+1)
			n--
		}
	}
	return s
}
